#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;

typedef int Vertex; /* 顶点编号类型 */

typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest; /* 边的另一端点编号 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj; /* 邻接表头指针 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed; /* true为有向图，false为无向图 */
};

typedef struct EulerNode *ECList; /* 欧拉回路链表 */
struct EulerNode {
    Vertex ver; /* 顶点编号 */
    ECList next; /* 线性表中下一个元素的位置 */
};
typedef struct CircPtrNode *Circuit; /* 欧拉回路 */
struct CircPtrNode {
    ECList first; /* 回路首结点指针 */
    ECList last; /* 回路尾结点指针 */
};

void InitGraph(LGraph graph, int kMaxVertex, bool directed) {
    /* 初始化一个空的图 */
    Vertex v;
    Position p;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明邻接表头结点数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (AdjList *)malloc(sizeof(AdjList) * kMaxVertex);
    for (v = 0; v < kMaxVertex; v++) {
        graph->ver_list[v] = (AdjList)malloc(sizeof(struct HeadNode));
        graph->ver_list[v]->adj = NULL;
    }
    graph->directed = directed;
}

void InsertEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;

    p = (Position)malloc(sizeof(struct EdgeNode));
    p->dest = v;
    p->next = graph->ver_list[u]->adj;
    graph->ver_list[u]->adj = p;
    graph->m_edges++;
    if (graph->directed ==
                false) { /* 如果是无向图，还要将u插入v的边表中 */
        p = (Position)malloc(sizeof(struct EdgeNode));
        p->dest = u;
        p->next = graph->ver_list[v]->adj;
        graph->ver_list[v]->adj = p;
    }
}

void RemoveEdge(LGraph graph, Vertex u, Vertex v) {
    Position p, deleted;
    bool success = false;

    p = graph->ver_list[u]->adj;
    if (p == NULL) {
        printf("错误：待删除的边不存在\n");
    } else if (p->dest == v) { /* 删除第1个结点 */
        graph->ver_list[u]->adj = p->next;
        free(p);
        graph->m_edges--;
        success = true;
    } else {
        while (p->next != NULL && p->next->dest != v) {
            p = p->next;
        }
        if (p->next != NULL) { /* 删除v结点 */
            deleted = p->next;
            p->next = deleted->next;
            free(deleted);
            graph->m_edges--;
            success = true;
        } else {
            printf("错误：待删除的边不存在\n");
        }
    }
    if (graph->directed == false && success == true) {
        /* 无向图已经成功删除了<u,v>，还需要删除<v,u> */
        p = graph->ver_list[v]->adj;
        if (p->dest == u) { /* 删除第1个结点 */
            graph->ver_list[v]->adj = p->next;
            free(p);
        } else {
            while (p->next != NULL && p->next->dest != u) {
                p = p->next;
            }
            deleted = p->next;
            p->next = deleted->next;
            free(deleted);
        }
    }
}

LGraph Clone(LGraph graph) {
    /* 克隆原图的副本 */
    LGraph tmp_graph;
    Vertex v;
    Position p, tp;

    /* 创建空的副本图 */
    tmp_graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(tmp_graph, graph->n_verts, graph->directed);
    /* 以下开始复制 */
    tmp_graph->n_verts = graph->n_verts;
    tmp_graph->m_edges = graph->m_edges;
    for (v = 0; v < tmp_graph->n_verts; v++) {
        p = graph->ver_list[v]->adj;
        /* 方便起见创建临时空头结点 */
        tmp_graph->ver_list[v]->adj = (Position)malloc(sizeof(struct EdgeNode));
        tp = tmp_graph->ver_list[v]->adj;
        while (p != NULL) {
            tp->next = (Position)malloc(sizeof(struct EdgeNode));
            tp->next->dest = p->dest;
            p = p->next;
            tp = tp->next;
        }
        tp->next = NULL;
        /* 删除临时空头结点 */
        tp = tmp_graph->ver_list[v]->adj;
        tmp_graph->ver_list[v]->adj = tp->next;
        free(tp);
    }
    return tmp_graph;
}

/* 算法7-20：从给定点出发获得一条回路 GetCircuit(graph, start) */
Circuit GetCircuit(LGraph graph, Vertex start) {
    ECList new_node;
    Circuit circuit;
    Position p;
    Vertex head, tail;

    new_node = (ECList)malloc(sizeof(struct EulerNode));
    new_node->ver =
        start; /* 从start顶点开始，构造回路的第一个结点 */
    new_node->next = NULL;
    circuit = (Circuit)malloc(sizeof(struct CircPtrNode));
    circuit->first = new_node;
    circuit->last = new_node;
    head = start; /* 从start开始寻找回路 */
    p = graph->ver_list[head]->adj;
    while (p != NULL) {
        tail = p->dest; /* 当前经过<head, tail>这条边 */
        RemoveEdge(graph, head, tail); /* 将经过的边删除，避免重复经过 */
        new_node = (ECList)malloc(sizeof(struct EulerNode));
        new_node->ver = tail; /* 将tail收入回路 */
        new_node->next = NULL;
        circuit->last->next = new_node;
        circuit->last = circuit->last->next;
        if (tail == start) { /* 回路结束，跳出循环 */
            break;
        }
        head = tail; /* 更新起始点，继续 */
        p = graph->ver_list[head]->adj;
    }
    return circuit;
}
/* 算法7-20 结束 */

/* 算法7-21：求欧拉回路 EulerCircle(graph) */
Circuit EulerCircle(LGraph graph) {
    Vertex v;
    Position p;
    ECList cp;
    int degree;
    LGraph tmp_graph;
    Circuit circuit, next_circuit;

    for (v = 0; v < graph->n_verts;
            v++) { /* 计算每个顶点的度，判断是否存在欧拉回路 */
        p = graph->ver_list[v]->adj;
        degree = 0;
        while (p != NULL) {
            degree++;
            p = p->next;
        }
        if (degree % 2 == 1) {
            return NULL; /* 存在度为奇数的顶点，该无向连通图无欧拉回路 */
        }
    }
    tmp_graph = Clone(graph); /* 复制原图的副本 */
    circuit = GetCircuit(tmp_graph,
                         0); /* 从0下标顶点开始，构造第一个当前结果回路 */
    cp = circuit->first->next; /* 寻找新的回路，并入当前结果回路中 */
    while (cp != NULL) {
        if (tmp_graph->ver_list[cp->ver]->adj != NULL) { /* 找到第1个起始顶点 */
            next_circuit = GetCircuit(tmp_graph, cp->ver); /* 找下一个回路 */
            next_circuit->last->next = cp->next; /* 合并到主回路 */
            cp->next = next_circuit->first->next;
            free(next_circuit->first); /* 删除重复的头结点 */
        }
        cp = cp->next;
    }
    return circuit;
}
/* 算法7-21 结束 */

LGraph BuildGraph() {
    LGraph graph;
    int kMaxVertex, n, m, i;
    Vertex u, v;

    scanf("%d\n", &kMaxVertex);
    graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(graph, kMaxVertex, false);
    scanf("%d %d\n", &n, &m);
    graph->n_verts = n;
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        InsertEdge(graph, u, v);
    }
    return graph;
}

int main(void) {
    LGraph graph;
    Circuit circuit;
    ECList cp;

    graph = BuildGraph();
    circuit = EulerCircle(graph);
    if (circuit != NULL) {
        for (cp = circuit->first; cp != circuit->last; cp = cp->next) {
            printf("%d->", cp->ver);
        }
        printf("%d\n", cp->ver);
    } else {
        printf("No Euler circuit.\n");
    }

    return 0;
}